home *** CD-ROM | disk | FTP | other *** search
/ Megadoom II / MEGADOOM II - iso.7z / MEGADOOM II.ISO / doom / editors / wadfile / warm11 / blockmap.c next >
C/C++ Source or Header  |  1994-12-21  |  9KB  |  219 lines
  1. /******************************************************************************
  2.     MODULE:        BLOCKMAP.C
  3.     WRITTEN BY:    Robert Fenske, Jr. (rfenske@swri.edu)
  4.                 Southwest Research Institute
  5.                 Electromagnetics Division
  6.                 6220 Culebra
  7.                 San Antonio, Texas 78238-5166
  8.     CREATED:    Feb. 1994
  9.     DESCRIPTION:    This module contains routines to generate the BLOCKMAP
  10.             section.  See the generation routine for an explanation
  11.             of the method used to generate the BLOCKMAP.  The
  12.             optimizations for the horizontal LINEDEF, vertical
  13.             LINEDEF, and single block cases came from ideas
  14.             presented in the Unofficial DOOM Specs written by
  15.             Matt Fell.
  16.  
  17.             DOOM is a trademark of id Software, Inc.
  18. ******************************************************************************/
  19. #include <stdio.h>
  20. #include <stdlib.h>
  21. #include <math.h>
  22. #include "dmglobal.i"
  23.  
  24. local short *Blockmap;                /* built BLOCKMAP */
  25.  
  26.  
  27. /******************************************************************************
  28.     ROUTINE:    blockmap_add_line(block,lndx,nlines)
  29.     WRITTEN BY:    Robert Fenske, Jr.
  30.     CREATED:    Feb. 1994
  31.     DESCRIPTION:    This routine adds the LINEDEF lndx to the block's
  32.             block LINEDEF list.  If no list exists yet for the
  33.             block, one is created.  Memory is allocated for no more
  34.             than thirty LINEDEFS (to save memory); only if more
  35.             than thirty LINEDEFS are in a single block is more
  36.             memory allocated.
  37. ******************************************************************************/
  38. #if defined(ANSI_C)
  39. local void blockmap_add_line(register short **block, int lndx, long nlines)
  40. #else
  41. local void blockmap_add_line(block,lndx,nlines)
  42. register short **block;
  43. int lndx;
  44. long nlines;
  45. #endif
  46. {
  47.   short *newblock;
  48.   int nmax = min(nlines,30);
  49.   register int k;
  50.  
  51.   if (*block == NULL) {                /* allocate if no list yet */
  52.     *block = blockmem(short,nmax);
  53.     (*block)[nmax-1] = -1;
  54.   }
  55.   for (k = 0; 0 < (*block)[k]; k++);        /* seek to end of list */
  56.   if ((*block)[k] == -1) {
  57.     newblock = blockmem(short,k+1+nmax);
  58.     blockcopy(newblock,*block,(k+1)*sizeof(**block));
  59.     blockfree(*block);
  60.     *block = newblock;
  61.     (*block)[k+1+nmax-1] = -1;
  62.   }
  63.   (*block)[k] = lndx+1;                /* add this LINEDEF */
  64. }
  65.  
  66.  
  67. /******************************************************************************
  68.     ROUTINE:    blockmap_make(blockmap,lines,nlines,verts)
  69.     WRITTEN BY:    Robert Fenske, Jr.
  70.     CREATED:    Feb. 1994
  71.     DESCRIPTION:    This routine builds the BLOCKMAP section given the
  72.             LINEDEFS and VERTEXES.  The BLOCKMAP section has the
  73.             following information (all are 16-bit words):
  74.  
  75.             block grid X origin
  76.             block grid Y origin
  77.             # blocks along X axis (total # blocks --> )
  78.             # blocks along Y axis (N = Xn * Yn        )
  79.             block 0 offset (# words)
  80.             block 1 offset (# words)
  81.                 .
  82.                 .
  83.             block N-1 offset (# words)
  84.             block 0 data (M words: 0,LINEDEFs in block 0,FFFF)
  85.             block 1 data (M words: 0,LINEDEFs in block 1,FFFF)
  86.                 .
  87.                 .
  88.             block N-1 data (M words: 0,LINEDEFs in block N-1,FFFF)
  89.  
  90.             Block 0 is at the lower left, block 1 is to the right
  91.             of block 0 along the x-axis, ..., block N-1 is at the
  92.             upper right.  An N-element pointer array is allocated
  93.             to hold pointers to the list of LINEDEFS in each block.
  94.             If no LINEDEFS occur within a block, it's pointer will
  95.             be NULL.  Then the LINEDEFS are scanned to find the
  96.             blocks each line occupies, building the lists of
  97.             LINEDEFS along the way.  Four cases are considered
  98.             for each LINEDEF.  The line is either diagonal,
  99.             horizontal, vertical, or resides in a single block
  100.             (regardless of orientation).  The non-diagonal cases
  101.             can be optimized since the blocks occupied can be
  102.             directly calculated.  The diagonal case basically
  103.             computes the blocks occupied on each row for all the
  104.             rows between the LINEDEF endpoints.  Once this is
  105.             complete the actual blockmap is allocated and filled.
  106.             It returns the number of words in the blockmap.
  107.     MODIFIED:        Robert Fenske, Jr.    Mar. 1994
  108.             Added in the optimizations for the orthogonal line
  109.             cases using the ideas presented in the Unofficial DOOM
  110.             Specs written by Matt Fell.
  111. ******************************************************************************/
  112. #if defined(ANSI_C)
  113. long blockmap_make(register short **blockmap, register DOOM_LINE *lines,
  114.                    long nlines, DOOM_VERT *verts)
  115. #else
  116. long blockmap_make(blockmap,lines,nlines,verts)
  117. register short **blockmap;            /* built BLOCKMAP */
  118. register DOOM_LINE *lines;            /* map LINEDEFS */
  119. long nlines;                    /* map # lines */
  120. DOOM_VERT *verts;                /* map VERTEXES */
  121. #endif
  122. {
  123.   short xmin,ymin, xmax,ymax;            /* map coords min/max */
  124.   long scl;                    /* line following scaling */
  125.   long size = 0x80;                /* block size (map coords) */
  126.   short xorig, yorig;                /* blockmap x,y origin */
  127.   short xn, yn;                    /* # blocks in x,y dirs */
  128.   long xcc, xcl;
  129.   long xf,yf, xt,yt;
  130.   long xd, yd;                    /* x direction, y direction */
  131.   long m;                    /* diagonal line slope */
  132.   int o;
  133.   int l, k, i;
  134.   int p = 0;                    /* increment to next block */
  135.   int c = 0;                    /* # blocks to consider */
  136.   register short **boxlist;            /* array of blocks' lists */
  137.   register long b;
  138.   register long t;
  139.  
  140.   xmin = ymin = (short)0x7FFF, xmax = ymax = (short)0x8000;
  141.   for (l = 0; l < nlines; l++) {        /* find min/max map coords */
  142.     xf = verts[lines[l].fndx].x, yf = verts[lines[l].fndx].y;
  143.     if (xf < xmin) xmin = (short)xf;        /* check from vertex */
  144.     if (yf < ymin) ymin = (short)yf;
  145.     if (xmax < xf) xmax = (short)xf;
  146.     if (ymax < yf) ymax = (short)yf;
  147.     xt = verts[lines[l].tndx].x, yt = verts[lines[l].tndx].y;
  148.     if (xt < xmin) xmin = (short)xt;        /* check to vertex */
  149.     if (yt < ymin) ymin = (short)yt;
  150.     if (xmax < xt) xmax = (short)xt;
  151.     if (ymax < yt) ymax = (short)yt;
  152.   }
  153.   xorig = xmin-8;                /* get x origin */
  154.   yorig = ymin-8;                /* get y origin */
  155.   xn = (xmax-xorig+size)/size;            /* get # in x direction */
  156.   yn = (ymax-yorig+size)/size;            /* get # in y direction */
  157.   boxlist = blockmem(short *,xn*yn);
  158.   scl = 81920L/(100+yn);            /* so scl*scl*size*yn<2^31-1 */
  159.   size *= scl;
  160.   t = 0;                    /* total len of all lists */
  161.   for (l = 0; l < nlines; l++) {        /* scan LINEDEFS here */
  162.     xf = scl*((long)verts[lines[l].fndx].x-(long)xorig);
  163.     yf = scl*((long)verts[lines[l].fndx].y-(long)yorig);
  164.     xt = scl*((long)verts[lines[l].tndx].x-(long)xorig);
  165.     yt = scl*((long)verts[lines[l].tndx].y-(long)yorig);
  166.     xd = sgn(xt-xf), yd = sgn(yt-yf);
  167.     switch (2*(xf/size == xt/size) + (yf/size == yt/size)) {
  168.      case  0: c=0,                             p=yd*xn;/* diagonal line */
  169.      bcase 1: c=abs((int)(xt/size-xf/size))+1, p=xd;/* horizontal line */
  170.      bcase 2: c=abs((int)(yt/size-yf/size))+1, p=yd*xn;/* vertical line */
  171.      bcase 3: c=0+1,                           p=1;/* start,end same block */
  172.     }
  173.     b = xf/size + xn*(yf/size);            /* start @ this block */
  174.     for (i = 0; i < c; i++, b+=p) {        /* add to lists for special */
  175.       blockmap_add_line(&boxlist[b],l,nlines);    /* cases: horizontal,       */
  176.       t++;                    /* vertical, & single block */
  177.     }
  178.     if (c == 0) {                /* handle diagonal lines */
  179.       m = scl*(yt-yf)/(xt-xf);            /* spanning > 1 block    */
  180.       if (m == 0) m = sgn(yt-yf)*sgn(xt-xf);    /* force a min non-0 slope */
  181.       xcl = xf;
  182.       if (yd == -1) xcc = xf + scl*((yf/size)*size -    1 - yf)/m;
  183.       else          xcc = xf + scl*((yf/size)*size + size - yf)/m;
  184.       do {
  185.         for (c = 0; c <= abs((int)(xcc/size - xcl/size)); c++, b+=xd) {
  186.           blockmap_add_line(&boxlist[b],l,nlines);
  187.           t++;
  188.         }
  189.         b += p-xd;
  190.         xcl = xcc, xcc += yd*scl*size/m;
  191.         if (xd*xcc > xd*xt) xcc = xt;        /* don't overrun endpoint */
  192.       } while (xd*xcl < xd*xt);
  193.     }
  194.   }
  195.   Blockmap = blockmem(short,4+xn*yn+t+2*xn*yn);
  196.   t = 0;
  197.   Blockmap[t++] = xorig;            /* fill in X,Y origin */
  198.   Blockmap[t++] = yorig;
  199.   Blockmap[t++] = xn;                /* fill in # in X and */
  200.   Blockmap[t++] = yn;                /* Y directions       */
  201.   o = t;
  202.   t += xn*yn;
  203.   for (i = 0; i < xn*yn; i++) {            /* now fill in BLOCKMAP */
  204.     Blockmap[o++] = t;                /* offset in BLOCKMAP */
  205.     Blockmap[t++] = 0;                /* always zero */
  206.     if (boxlist[i] != NULL) {
  207.       for (k = 0; 0 < boxlist[i][k]; k++)    /* list of lines in this */
  208.         Blockmap[t++] = boxlist[i][k]-1;    /* block                 */
  209.       blockfree(boxlist[i]);
  210.     }
  211.     Blockmap[t++] = -1;                /* always -1 */
  212.     if (t >= 65536L)                /* remaining offsets are bad */
  213.       printf("\n<<error: BLOCKMAP too large; must reduce map size>>\n");
  214.   }
  215.   blockfree(boxlist);
  216.   if (blockmap != NULL) *blockmap = Blockmap;
  217.   return t;                    /* # words in BLOCKMAP */
  218. }
  219.